package sort;

import java.util.Arrays;

/**
 * @Author Zhouchb
 * @Create 2021-10-2021/10/26 :9:15
 * @Description
 */
public class QuickSort {
/*    public static void main(String[] args) {
        int[] arr={9,1, 2, 5, 7, 4, 8, 6,3,5};//直接复制数组
//       int[] arr={3,1,4,2,5};//直接复制数组
        quick_sort(arr,0,arr.length-1);
        print(arr);
    }
    private static int get_mid(int arr[],int left,int right){
        int pivot=arr[left];
        while(left<right){//当left与right指针相遇的时候退出循环，双指针遍历结束
            while(arr[right]>=pivot && left<right) right--;
            arr[left]=arr[right];
            while(arr[left]<=pivot && left<right) left++;
            arr[right]=arr[left];
        }
        //经历了上面的循环实现了pivot为中轴，小放左，大放右的格局
        arr[left]=pivot;//最后把存放在pivot值放回数组空arr[left]中
        return left;//返回中轴所在的下标位置。
    }

    private static void  quick_sort(int[] arr,int left,int right){
        if(left<right){
//            将arr[left..right]均分为两部分arr[left..mid]和arr[mid+1..right]
//             * ,以pivot为中轴，小放左，大放右。这是第一步。
            int mid =get_mid(arr,left,right);//接收中轴所在的下标位置。
            quick_sort(arr,left,mid-1);
            quick_sort(arr,mid+1,right);
        }
    }

    public static void print(int arr[])//封装函打印函数
    {
        for(int k=0;k<arr.length;k++)
        {
            System.out.print(arr[k]+" ");
        }
    }}*/
   public static void main(String[] args) {
       // int arr[] = {6,4,9,5,7,1,3,8};
       int arr[] = {9,1, 2, 5, 7, 4, 8, 6,3,5};
       sort(arr,0,arr.length-1);
       System.out.println(Arrays.toString(arr));
   }

   public static void sort(int arr[],int l,int r){
       if (l<r){
           int mid =quickSort(arr,l,r);
           sort(arr,l,mid-1);
           sort(arr,mid+1,r);
       }
   }
    private static int  quickSort(int[] arr, int l, int r) {
       int temp = arr[l];
       while (l<r){
           while (arr[r]>=temp && l<r){
               r--;
           }
           if (l<r){
               arr[l]=arr[r];
           }
           while (arr[l]<=temp && l<r){
              l++;
           }
           if (l<r){
               arr[r]=arr[l];
           }
       }
       arr[l]=temp;
       return l;
    }

}


//////////////////////////
class quicksort{
    public static void main(String[] args) {
        int[] arr = new int[]{4,3,7,5,33,3};
        sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr,int l,int r){
        if (l>=r){
            return;
        }
        int mid = partition(arr,l,r);
        sort(arr,l,mid-1);
        sort(arr,mid+1,r);
    }
    public static int partition(int[] arr,int l,int r){
        int key = arr[l];
        while (l<r){
            while (key<=arr[r]&&l<r){
                r--;
            }
            arr[l]=arr[r];
            while (key>=arr[l]&&l<r){
                l++;
            }
            arr[r]=arr[l];
        }
        arr[l]=key;
        return l;
    }

}